Outline for INF-42 Written Final Exam

I have collected together in this one handout the list of topics that we have covered in the second half of INF-42. Use it in conjunction with the first topic list to better understand what will be on the final exam (which will be about 1/3 topics from the first half material and 2/3 topics from the second half).

Therefore, you should concentrate on reviewing the most important analysis and synthesis skills that we have studied. Use the quizzes, the programming assignments, and programming exams as a guide for what material is of primary importance. Understand the material on its own terms, and how to use this material when writing code. Certainly using and writing classes has been the central theme of the first half of this course, which involves knowing how to use all of Java's control structures and arrays. For the second half of the course, we studied inheritance, analysis of algorithms, the structure and use of collection classes, and writing classes for and code that processes linked lists and trees.

My written exams are not designed to determine if you understand obscure material; instead, they are designed to determine if you understand important material, and can use your knowledge to understand and answer questions quickly. My exams are long (some students will not finish them): it you don't immediately know the answer to a question, skip it, and come back to it later, if you have time (sometimes working problems later in the exam will remind you of something relevant to the answer to earlier questions).

Outline of Lecture Topics

• Inheritance in Classes
  • Superclasses and subclasses (using extends)
  • Inheritance of state
  • Inheritance of methods (straight inheritance and overriding; use of .super)
  • Compile time (variable types) and runtime (object classes) behavior
  • Use of superclass constructors in subclass constructors (another use of .super)
  • Abstract classes (and extending them to be concrete classes)

• Analysis of Algorithms
  • Meaning of big-O notation (discarding constants and lower order terms)
  • Complexity classes (by inspection of algorithm; empirical measurements)
  • Combining complexity classes
  • Complexity classes of basic algorithms on arrays, hash tables, lists, trees (e.g., searching and sorting)
  • Predicting running times from complexity classes and one time measurement

• Collection Classes
  • Interfaces (e.g., List) and Classes (e.g., ArrayList)
  • Ordered Collections: Stack, Queue, Priority Queue
  • Collections: List, Set
  • Maps: Map and Map.Entry
  • Constructors and common methods
  • Iterators, including remove and ConcurrentModificationException
  • Hash tables for O(1) add/contains/remove methods in sets and maps
  • Sorting lists (with and without a Comparator) using Collections.sort
  • Classes with generics, including special iterator: for (type variable : collection)

• Linear Lists
  • Self-referential classes (e.g., LN)
  • Traversing linked lists using cursors
  • Building linked-list in order and in reverse order (caching a reference to the rear of the list)
  • Insertion (at the front and rear)
  • Search and remove methods
  • Introduction to special lists: circular, header, trailer, doubly-linked
  • Implementing collection classes with linked lists (e.g., a front instance variable, often caching size)

• Recursion
  • General Principles
  • Hand simulation
  • Proof rules
  • For processing linked lists: accessors and mutators

• Trees
  • Terminology
  • Self-referential classes for Binary Trees (e.g., TN)
  • Recursive size and height methods
  • size and height relationships of pathological and bushy trees.

• Binary Search Trees
  • Order property (arbitary sructure property)
  • Iterative and Recursive Processsing
  • Basic Algorithms: Searching, Insertion, Deletion (on pictures)
  • Traversal Orders: preorder, inorder, postorder, breadth first

  ---